#ifndef LEETCODE_CN_CPP_JIANZHI_4_H
#define LEETCODE_CN_CPP_JIANZHI_4_H

#include <algorithm>
#include <vector>

using namespace std;

namespace jianzhi_4
{

class Solution
{
public:
    // bool findNumberIn2DArray(vector<vector<int>> &matrix, int target)
    // {
    //     for (const auto &row : matrix)
    //     {
    //         if (row.empty() || target > row.back())
    //         {
    //             continue;
    //         }
    //         if (target < row.front())
    //         {
    //             return false;
    //         }
    //         if (binary_search(row.begin(), row.end(), target))
    //         {
    //             return true;
    //         }
    //     }
    //     return false;
    // }

    // optimized 从右上角开始找，如果小就左移，大就右移
    bool findNumberIn2DArray(vector<vector<int>> &matrix, int target)
    {
        if (matrix.empty() || matrix[0].empty())
        {
            return false;
        }
        int rows = matrix.size(), cols = matrix[0].size();
        int i = 0, j = cols - 1;
        while (i < rows && j >= 0)
        {
            auto n = matrix[i][j];
            if (n == target)
            {
                return true;
            }
            else if (n > target)
            {
                j--;
            }
            else
            {
                i++;
            }
        }
        return false;
    }
};

} // namespace jianzhi_4

#endif //LEETCODE_CN_CPP_JIANZHI_4_H
